/*
在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

（请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。

返回区域的数目。

 

示例 1：

输入：
[
  " /",
  "/ "
]
输出：2
解释：2x2 网格如下：

示例 2：

输入：
[
  " /",
  "  "
]
输出：1
解释：2x2 网格如下：

示例 3：

输入：
[
  "\\/",
  "/\\"
]
输出：4
解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
2x2 网格如下：

示例 4：

输入：
[
  "/\\",
  "\\/"
]
输出：5
解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
2x2 网格如下：

示例 5：

输入：
[
  "//",
  "/ "
]
输出：3
解释：2x2 网格如下：

 

提示：

1 <= grid.length == grid[0].length <= 30
grid[i][j] 是 '/'、'\'、或 ' '。

*/

#include "stdc++.h"

/* 并查集
*/
class UnionFind {
public:
    UnionFind(int n) : n(n), count(n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i{0}; i < n; ++i) {
            parent[i] = i;
        }
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    int unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        if (size[x] < size[y]) {
            swap(x, y);
        }
        --count;
        size[x] += size[y];
        parent[rootY] = parent[rootX];
        return true;
    }
    int getCount() {
        return count;
    }
private:
    vector<int> parent;
    vector<int> size;
    int n;
    int count; // 连通区域的个数
};

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        UnionFind* uf = new UnionFind(n * n * 4);
        for (int i{0}; i < n; ++i) {
            for (int j{0}; j < n; ++j) {
                // 上、右、下、左的顺序依次编号 0, 1, 2, 3
                int index = i * n + j; // 二维坐标转换成一维坐标
                if (i < n - 1) {
                    int bottom = index + n; // 向下一个坐标
                    uf->unite(index * 4 + 2, bottom * 4);
                }
                if (j < n - 1) {
                    int right = index + 1; // 向右一个坐标
                    uf->unite(index * 4 + 1, right * 4 + 3);
                }
                if (grid[i][j] == '/') {
                    uf->unite(index * 4, index * 4 + 3);
                    uf->unite(index * 4 + 1, index * 4 + 2);
                } else if (grid[i][j] == '\\') {
                    uf->unite(index * 4, index * 4 + 1);
                    uf->unite(index * 4 + 2, index * 4 + 3);
                } else {
                    uf->unite(index * 4, index * 4 + 1);
                    uf->unite(index * 4 + 1, index * 4 + 2);
                    uf->unite(index * 4 + 2, index * 4 + 3);
                }
            }
        }
        return uf->getCount();
    }
};

class UnionFind {
public:
    UnionFind(int n) : count(n) {
        parent.resize(n);
        for (int i{0}; i < n; ++i) {
            parent[i] = i;
        }
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        --count;
        parent[rootY] = parent[rootX];
    }
    int getCount() {
        return count;
    }
private:
    vector<int> parent;
    int count; // 连通区域的个数
};

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        UnionFind* uf = new UnionFind(n * n * 4);
        for (int i{0}; i < n; ++i) {
            for (int j{0}; j < n; ++j) {
                // 上、右、下、左的顺序依次编号 0, 1, 2, 3
                int index = i * n + j; // 二维坐标转换成一维坐标
                if (i < n - 1) {
                    int bottom = index + n; // 向下一个坐标
                    uf->unite(index * 4 + 2, bottom * 4);
                }
                if (j < n - 1) {
                    int right = index + 1; // 向右一个坐标
                    uf->unite(index * 4 + 1, right * 4 + 3);
                }
                if (grid[i][j] == '/') {
                    uf->unite(index * 4, index * 4 + 3);
                    uf->unite(index * 4 + 1, index * 4 + 2);
                } else if (grid[i][j] == '\\') {
                    uf->unite(index * 4, index * 4 + 1);
                    uf->unite(index * 4 + 2, index * 4 + 3);
                } else {
                    uf->unite(index * 4, index * 4 + 1);
                    uf->unite(index * 4 + 1, index * 4 + 2);
                    uf->unite(index * 4 + 2, index * 4 + 3);
                }
            }
        }
        return uf->getCount();
    }
};